import functools


class Solution(object):
    def findMinStep(self, board, hand):
        """
        :type board: str
        :type hand: str
        :rtype: int
        """
        hand = list(hand)
        hand.sort()
        hand = ''.join(hand)

        @functools.cache
        def convert(s):
            t = ''
            n = len(s)
            left_index = 0
            right_index = 0
            while right_index < n:
                if s[right_index] != s[left_index]:
                    if right_index - left_index < 3:
                        t += s[left_index: right_index]
                    left_index = right_index
                right_index += 1
            if right_index - left_index < 3:
                t += s[left_index: right_index]
            if len(t) < len(s):
                return convert(t)
            else:
                return t

        @functools.cache
        def search(board, hand):
            if board and not hand:
                return -1
            if not board:
                return 0
            min_flag = False
            for i in range(len(hand)):
                for j in range(len(board)):
                    if hand[i] == board[j] or (j > 0 and board[j - 1] == board[j]):
                        new_board = convert(board[0:j] + hand[i] + board[j:])
                        val = search(new_board, hand[:i] + hand[i + 1:])
                        if val >= 0:
                            if not min_flag:
                                min_flag = True
                                min_count = val + 1
                            else:
                                min_count = min(min_count, val + 1)
            if not min_flag:
                return - 1
            else:
                return min_count

        return search(board, hand)


data = Solution()
board = "WRRBBW"
hand = "RBW"
print(data.findMinStep(board, hand))
board = "RRWWRRBBRR"
hand = "WB"
print(data.findMinStep(board, hand))
board = "BGBBYRYYRBRWYBRR"
hand = "YWYRB"
print(data.findMinStep(board, hand))

